package leecode.二分法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class 寻找k个最接近的数 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        List<Integer> list = solution.findClosestElements2(new int[]{0,1,2,3,4,5,6}, 5, 7);
        System.out.println(list.toString());
        System.out.println(5>>>1);
        String s = new String();

    }



    static class Solution {
        public List<Integer> findClosestElements(int[] arr, int k, int x) {
            int left=0,size=arr.length,right=size-1;
            int removenums = size-k;
            while (removenums>0){
                if (x-arr[left]<=arr[right]-x){
                    right--;
                }else {
                    left++;
                }
                removenums--;
            }

            ArrayList<Integer> list = new ArrayList<>();
            for (int i = left ; i < left+k ; i++) {
                list.add(arr[i]);
            }
            return list;
        }

        public List<Integer> findClosestElements2(int[] arr, int k, int x) {
            int size = arr.length;

            int left = 0;
            int right = size - k;

            while (left < right) {
                // int mid = left + (right - left) / 2;
                int mid = (left + right) >>> 1;
                // 尝试从长度为 k + 1 的连续子区间删除一个元素
                // 从而定位左区间端点的边界值
                if (x - arr[mid] > arr[mid + k] - x) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }

            List<Integer> res = new ArrayList<>();
            for (int i = left; i < left + k; i++) {
                res.add(arr[i]);
            }
            return res;
        }



    }
}


